<html>
 <head>
  <meta charset="UTF-8">
 </head>
 <body>
  <h1 data-lake-id="BoTE7" id="BoTE7"><span data-lake-id="ue45f27ee" id="ue45f27ee">典型回答</span></h1>
  <p data-lake-id="uaa69bd8d" id="uaa69bd8d"><br></p>
  <p data-lake-id="ub69c9d86" id="ub69c9d86"><span data-lake-id="u1daa8f06" id="u1daa8f06">LRU算法的思想是：如果一个数据在最近一段时间没有被访问到，那么可以认为在将来它被访问的可能性也很小。因此，当空间满时，最久没有访问的数据最先被淘汰。</span></p>
  <p data-lake-id="ubdbb6377" id="ubdbb6377"><span data-lake-id="u77a022e8" id="u77a022e8">​</span><br></p>
  <p data-lake-id="u31b8dd8e" id="u31b8dd8e"><span data-lake-id="u1581cf0c" id="u1581cf0c">一般实现有两种方式，首先是</span><strong><span data-lake-id="ua24d3013" id="ua24d3013">通过继承LinkedHashMap可以实现这个功能</span></strong><span data-lake-id="u8526471f" id="u8526471f">。</span></p>
  <p data-lake-id="ubffce11b" id="ubffce11b"><span data-lake-id="ue0f88dcf" id="ue0f88dcf">​</span><br></p>
  <p data-lake-id="u63b8b555" id="u63b8b555"><span data-lake-id="u9ff76978" id="u9ff76978">LinkedHashMap内部维护了一个双向链表，用于存储元素的顺序信息。当accessOrder参数为true时，LinkedHashMap会按照访问顺序来维护元素，即最近访问的元素会被移到链表尾部，而最久未使用的元素会被移到链表头部。当accessOrder参数为false时，LinkedHashMap会按照插入顺序来维护元素。</span></p>
  <p data-lake-id="ueb93b7eb" id="ueb93b7eb"><span data-lake-id="uee36b217" id="uee36b217">​</span><br></p>
  <p data-lake-id="u3f0d96d8" id="u3f0d96d8"><span data-lake-id="uad4d5743" id="uad4d5743">​</span><br></p>
  <p data-lake-id="uda889f9b" id="uda889f9b"><span data-lake-id="u2138d14e" id="u2138d14e">LinkedHashMap和HashMap一样提供了put、get等方法，实现细节稍有不同（以下特点为当accessOrder为true时）：</span></p>
  <p data-lake-id="u8ac7ef2f" id="u8ac7ef2f"><span data-lake-id="u1ac89f19" id="u1ac89f19">​</span><br></p>
  <ul list="uf28f0879" data-lake-index-type="true">
   <li fid="u76af44c7" data-lake-id="u281f2a65" id="u281f2a65"><span data-lake-id="u436d0b35" id="u436d0b35">put方法：</span></li>
  </ul>
  <ul list="uf28f0879" data-lake-indent="1" data-lake-index-type="true">
   <li fid="u0ca21185" data-lake-id="ubea08add" id="ubea08add"><span data-lake-id="ud55d5cf5" id="ud55d5cf5">如果指定的键已经存在，则更新对应的值，并将该元素移动到链表末尾</span></li>
   <li fid="u0ca21185" data-lake-id="ubf564de7" id="ubf564de7"><span data-lake-id="u6fd39207" id="u6fd39207">如果指定的键不存在，则将新元素插入到哈希表中，并将其插入到链表末尾</span></li>
  </ul>
  <ul list="uf28f0879" start="2" data-lake-index-type="true">
   <li fid="u76af44c7" data-lake-id="ud2b1a27b" id="ud2b1a27b"><span data-lake-id="u6744d128" id="u6744d128">get方法：</span></li>
  </ul>
  <ul list="u4a3860ad" data-lake-indent="1" data-lake-index-type="true">
   <li fid="u030f3bff" data-lake-id="udeaf6eaf" id="udeaf6eaf"><span data-lake-id="u40237aa5" id="u40237aa5">如果指定的键不存在，则返回</span><span data-lake-id="u0f76d8cc" id="u0f76d8cc">null</span><span data-lake-id="u007971bd" id="u007971bd">；</span></li>
   <li fid="u030f3bff" data-lake-id="u6dc86539" id="u6dc86539"><span data-lake-id="u2b28d1fe" id="u2b28d1fe">如果指定的键存在，则返回对应的值，并将该元素移动到链表末尾</span></li>
  </ul>
  <p data-lake-id="ue63dff76" id="ue63dff76"><span data-lake-id="u7cc9553d" id="u7cc9553d">​</span><br></p>
  <p data-lake-id="uf8fb1816" id="uf8fb1816"><span data-lake-id="ucc2c0a43" id="ucc2c0a43">但是，需要注意的是，LinkedHashMap默认情况下不会移除元素的，不过，LinkedHashMap中预留了方法afterNodeInsertion，在插入元素之后这个方法会被回调，这个方法的默认实现如下：</span></p>
  <p data-lake-id="u784add69" id="u784add69"><span data-lake-id="u57dab8b9" id="u57dab8b9">​</span><br></p>
  <pre lang="java"><code>
void afterNodeInsertion(boolean evict) { 
   LinkedHashMap.Entry&lt;K,V&gt; first;
   if (evict &amp;&amp; (first = head) != null &amp;&amp; removeEldestEntry(first)) {
       K key = first.key;
       removeNode(hash(key), key, null, false, true);
   }
}

protected boolean removeEldestEntry(Map.Entry&lt;K,V&gt; eldest) {
   return false;
}
</code></pre>
  <p data-lake-id="u3f3c1848" id="u3f3c1848"><br></p>
  <p data-lake-id="u8255e115" id="u8255e115"><span data-lake-id="u3a5f0290" id="u3a5f0290">可以看到，如果我们可以实现removeEldestEntry方法， 让他返回true的话，就可以执行删除节点的动作。所以，一个基于</span><strong><span data-lake-id="uf65d2780" id="uf65d2780">LinkedHashMap的LRU实现如下：</span></strong></p>
  <p data-lake-id="ucbcea87f" id="ucbcea87f"><strong><span data-lake-id="u7f8b2b45" id="u7f8b2b45">​</span></strong><br></p>
  <pre lang="java"><code>
import java.util.*;

public class LRUCache&lt;K, V&gt; extends LinkedHashMap&lt;K, V&gt; {
    private final int capacity;

    public LRUCache(int capacity) {
        // 调用LinkedHashMap构造函数，设置初始容量和负载因子
        super(capacity, 0.75f, true);
        this.capacity = capacity;
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry&lt;K, V&gt; eldest) {
        // 重写LinkedHashMap的removeEldestEntry方法，实现LRU缓存淘汰策略
        // 当缓存容量超出设定值时，自动移除最久未使用的元素
        return size() &gt; capacity;
    }
}
</code></pre>
  <p data-lake-id="ue0612826" id="ue0612826"><br></p>
  <p data-lake-id="u9f7991aa" id="u9f7991aa"><span data-lake-id="ud510df1c" id="ud510df1c">以上，就是一个最简单的LRU 缓存的实现方式了。</span></p>
  <p data-lake-id="u015f6714" id="u015f6714"><span data-lake-id="u5bde11ce" id="u5bde11ce">​</span><br></p>
  <p data-lake-id="u9a5e827e" id="u9a5e827e"><span data-lake-id="u3b6069c8" id="u3b6069c8">除此之外，还有一些其他的方式也可以实现，比如</span><strong><span data-lake-id="u51640192" id="u51640192">基于LinkedList+HashMap也可以简单的实现</span></strong><span data-lake-id="u3e9a3ca7" id="u3e9a3ca7">：</span></p>
  <p data-lake-id="uaa22e1fb" id="uaa22e1fb"><span data-lake-id="ubd86f76b" id="ubd86f76b">​</span><br></p>
  <pre lang="java"><code>
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;

public class LRUCache&lt;K, V&gt; {

    private final int capacity;            // 缓存容量
    private final Map&lt;K, V&gt; cache;         // 缓存
    private final LinkedList&lt;K&gt; keyList;   // 缓存key列表，用于记录key的访问顺序

    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.cache = new HashMap&lt;&gt;(capacity);
        this.keyList = new LinkedList&lt;&gt;();
    }

    // put操作：向缓存中存入一个key-value
    public synchronized void put(K key, V value) {
        // 如果缓存中已经存在该key，则需要将其从缓存中移除，因为它将被更新
        if (cache.containsKey(key)) {
            keyList.remove(key);
        }
        // 如果缓存已满，则需要删除最久未使用的key-value，即keyList的第一个元素
        while (cache.size() &gt;= capacity) {
            K oldestKey = keyList.removeFirst();
            cache.remove(oldestKey);
        }
        // 将新的key-value存入缓存中，并将该key添加到keyList的末尾，表示最近被访问
        cache.put(key, value);
        keyList.addLast(key);
    }

    // get操作：根据key获取对应的value
    public synchronized V get(K key) {
        // 如果缓存中存在该key，则将其从keyList中移除，并添加到末尾表示最近被访问
        if (cache.containsKey(key)) {
            keyList.remove(key);
            keyList.addLast(key);
            return cache.get(key);
        }
        // 如果缓存中不存在该key，则返回null
        return null;
    }
}

</code></pre>
  <p data-lake-id="u2c7fd7e8" id="u2c7fd7e8"><span data-lake-id="u1605a1e8" id="u1605a1e8">​</span><br></p>
  <p data-lake-id="ud713c577" id="ud713c577"><span data-lake-id="ueaa2fba5" id="ueaa2fba5">借助LinkedList来保存key的访问情况，将新的key或者刚刚被访问的key放在末尾，这样在移除的时候，可以从队头开始移除元素。</span></p>
 </body>
</html>